package src.CodeTop;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 *  
 *
 * 示例 1:
 *
 *
 *
 * 输入: [1,2,3,null,5,null,4]
 * 输出: [1,3,4]
 * 示例 2:
 *
 * 输入: [1,null,3]
 * 输出: [1,3]
 * 示例 3:
 *
 * 输入: []
 * 输出: []
 *
 */

public class _199BinaryTreeRightSideView {
    public static void main(String[] args) {

    }

    public List<Integer> rightSideView(TreeNode root) {
        // 结果集
        List<Integer> target = new ArrayList<>();
        // 如果根节点为空
        if (root == null) {
            return target;
        }
        // 定义存放每一层结点的队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 将根节点放入队列中
        queue.add(root);
        // 当队列大于0时进入循环
        while (queue.size() > 0) {
            // 获取当前层的结点数
            int len = queue.size();
            // 遍历当前层结点
            for (int i = 0 ; i < len ; i++) {
                // 如果是最后一个结点
                if (i == len - 1) {
                    // 取出当前结点
                    TreeNode cur = queue.remove();
                    // 将数值加入到结果集中
                    target.add(cur.val);
                    // 查看左右结点
                    if (cur.left != null) {
                        queue.add(cur.left);
                    }
                    if (cur.right != null) {
                        queue.add(cur.right);
                    }
                }else {
                    // 取出当前结点
                    TreeNode cur = queue.remove();
                    // 查看左右结点
                    if (cur.left != null) {
                        queue.add(cur.left);
                    }
                    if (cur.right != null) {
                        queue.add(cur.right);
                    }
                }
            }
        }
        return target;
    }
}
